<!DOCTYPE html>
<html lang="zh">
    <head>
    <!--
        © Material Theme
        https://github.com/viosey/hexo-theme-material
        Version: 1.3.0 -->

    <!-- Title -->
    
    <title>
        
            JDK底层实现源码分析系列(三) LinkedList源码分析 | 
        
        Binux Blog
    </title>

    <!-- Favicons -->
    <link rel="icon shortcut" type="image/ico" href="http://on2bs9q7q.bkt.clouddn.com/avatar.png">
    <link rel="icon" sizes="192x192" href="http://on2bs9q7q.bkt.clouddn.com/favicon.png">
    <link rel="apple-touch-icon" href="http://on2bs9q7q.bkt.clouddn.com/favicon.png">

    <!-- Meta & Info -->
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible">
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <meta name="theme-color" content="#0097A7">
    <meta name="author" content="Binux">
    <meta name="description" content="一名正在崛起的Java后端工程师">
    <meta name="keywords" content="null,JDK,Source Code">

    <!--iOS -->
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
    <meta name="apple-mobile-web-app-title" content="Title">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <meta name="HandheldFriendly" content="True">
    <meta name="MobileOptimized" content="480">

    <!-- Add to homescreen for Chrome on Android -->
    <meta name="mobile-web-app-capable" content="yes">

    <!-- Add to homescreen for Safari on iOS -->
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <meta name="apple-mobile-web-app-title" content="Binux Blog">

    <!-- The Open Graph protocol -->
    <meta property="og:url" content="http://binux.cn">
    <meta property="og:type" content="blog">
    <meta property="og:title" content="JDK底层实现源码分析系列(三) LinkedList源码分析 | Binux Blog">
    <meta property="og:description" content="一名正在崛起的Java后端工程师">
    <meta property="og:article:tag" content="JDK"> <meta property="og:article:tag" content="Source Code"> 

    <!--[if lte IE 9]>
        <link rel="stylesheet" href="/css/ie-blocker.css">

        
            <script src="/js/ie-blocker.zhCN.js"></script>
        
    <![endif]-->

    <!-- Import CSS -->
    <link rel="stylesheet" href="/css/material.min.css">
    <link rel="stylesheet" href="/css/style.min.css">
    <!-- Config CSS -->


<!-- Other Styles -->
<style>
  body, html {
    font-family: Roboto, "Helvetica Neue", Helvetica, "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei", "微软雅黑", Arial, sans-serif;
  }

  a {
    color: #00838F;
  }

  .mdl-card__media,
  #search-label,
  #search-form-label:after,
  #scheme-Paradox .hot_tags-count,
  #scheme-Paradox .sidebar_archives-count,
  #scheme-Paradox .sidebar-colored .sidebar-header,
  #scheme-Paradox .sidebar-colored .sidebar-badge{
    background-color: #0097A7 !important;
  }

  /* Sidebar User Drop Down Menu Text Color */
  #scheme-Paradox .sidebar-colored .sidebar-nav>.dropdown>.dropdown-menu>li>a:hover,
  #scheme-Paradox .sidebar-colored .sidebar-nav>.dropdown>.dropdown-menu>li>a:focus {
    color: #0097A7 !important;
  }

  #post_entry-right-info,
  .sidebar-colored .sidebar-nav li:hover > a,
  .sidebar-colored .sidebar-nav li:hover > a i,
  .sidebar-colored .sidebar-nav li > a:hover,
  .sidebar-colored .sidebar-nav li > a:hover i,
  .sidebar-colored .sidebar-nav li > a:focus i,
  .sidebar-colored .sidebar-nav > .open > a,
  .sidebar-colored .sidebar-nav > .open > a:hover,
  .sidebar-colored .sidebar-nav > .open > a:focus,
  #ds-reset #ds-ctx .ds-ctx-entry .ds-ctx-head a {
    color: #0097A7 !important;
  }

  .toTop {
    background: #757575 !important;
  }

  .material-layout .material-post>.material-nav,
  .material-layout .material-index>.material-nav,
  .material-nav a {
    color: #757575;
  }

  #scheme-Paradox .MD-burger-layer {
    background-color: #757575;
  }

  #scheme-Paradox #post-toc-trigger-btn {
    color: #757575;
  }

  .post-toc a:hover {
    color: #00838F;
    text-decoration: underline;
  }
</style>


<!-- Theme Background Related-->

    <style>
      body{
        background-color: #F5F5F5;
      }

      /* blog_info bottom background */
      #scheme-Paradox .material-layout .something-else .mdl-card__supporting-text{
        background-color: #fff;
      }
    </style>




<!-- Fade Effect -->

    <style>
      .fade {
        transition: all 800ms linear;
        -webkit-transform: translate3d(0,0,0);
        -moz-transform: translate3d(0,0,0);
        -ms-transform: translate3d(0,0,0);
        -o-transform: translate3d(0,0,0);
        transform: translate3d(0,0,0);
        opacity: 1;
      }

      .fade.out{
        opacity: 0;
      }
    </style>



    <script src="/js/jquery.min.js"></script>
    <script src="/js/queue.js"></script>

    <!-- UC Browser Compatible -->
    <script>
        var agent = navigator.userAgent.toLowerCase();
        if(agent.indexOf('ucbrowser')>0) {
            document.write("<link rel=\"stylesheet\" href=\"/css/uc.css\">");
            alert('由于 UC 浏览器使用极旧的内核，而本网站使用了一些新的特性。\n为了您能更好的浏览，推荐使用 Chrome 或 Firefox 浏览器。');
        }
    </script>

    
    <!-- Baidu Analytics -->
    <script>
        var _hmt = _hmt || [];
        (function() {var hm = document.createElement('script');
        hm.src = 'https://hm.baidu.com/hm.js?c286c0c5e31950b803d5d56c74493f58';
        var s = document.getElementsByTagName('script')[0];
        s.parentNode.insertBefore(hm, s);
        })();
    </script>
    

    
    <!-- Google Analytics -->
    <script>
        (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
        (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
        m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
        })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
        ga('create', 'UA-92760839-1', 'auto');ga('send', 'pageview');
    </script>
    

    <!-- Bing Background -->
    

    <!-- Custom Head -->
    
</head>


    
        <body id="scheme-Paradox" class="lazy">
            <div class="material-layout  mdl-js-layout has-drawer is-upgraded">
                

                <!-- Main Container -->
                <main class="material-layout__content" id="main">

                    <!-- Top Anchor -->
                    <div id="top"></div>

                    
                        <!-- Hamburger Button -->
                        <button class="MD-burger-icon sidebar-toggle">
                            <span class="MD-burger-layer"></span>
                        </button>
                    

                    <!-- Post TOC -->

    
    <!-- Back Button -->
    <!--
    <div class="material-back" id="backhome-div" tabindex="0">
        <a class="mdl-button mdl-js-button mdl-js-ripple-effect mdl-button--icon"
           href="#" onclick="window.history.back();return false;"
           target="_self"
           role="button"
           data-upgraded=",MaterialButton,MaterialRipple">
            <i class="material-icons" role="presentation">arrow_back</i>
            <span class="mdl-button__ripple-container">
                <span class="mdl-ripple"></span>
            </span>
        </a>
    </div>
    -->

    <!-- Left aligned menu below button -->
    <button id="post-toc-trigger-btn"
        class="mdl-button mdl-js-button mdl-button--icon">
        <i class="material-icons">format_list_numbered</i>
    </button>

    <ul class="post-toc-wrap mdl-menu mdl-menu--bottom-left mdl-js-menu mdl-js-ripple-effect" for="post-toc-trigger-btn">
        <ol class="post-toc"><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#前言"><span class="post-toc-number">1.</span> <span class="post-toc-text">前言</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#Collection-大家族"><span class="post-toc-number">1.1.</span> <span class="post-toc-text">Collection 大家族</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#LinkedList-继承树"><span class="post-toc-number">1.2.</span> <span class="post-toc-text">LinkedList 继承树</span></a></li></ol></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#分析"><span class="post-toc-number">2.</span> <span class="post-toc-text">分析</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#链表和数组"><span class="post-toc-number">2.1.</span> <span class="post-toc-text">链表和数组</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#new"><span class="post-toc-number">2.2.</span> <span class="post-toc-text">new</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#插入数据"><span class="post-toc-number">2.3.</span> <span class="post-toc-text">插入数据</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#删除数据"><span class="post-toc-number">2.4.</span> <span class="post-toc-text">删除数据</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#修改数据"><span class="post-toc-number">2.5.</span> <span class="post-toc-text">修改数据</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#查询数据"><span class="post-toc-number">2.6.</span> <span class="post-toc-text">查询数据</span></a></li></ol></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#总结"><span class="post-toc-number">3.</span> <span class="post-toc-text">总结</span></a></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#著作权声明"><span class="post-toc-number">4.</span> <span class="post-toc-text">著作权声明</span></a></li></ol>

        <!--
        <li class="mdl-menu__item">
            Some Action
        </li>
        -->
    </ul>




<!-- Layouts -->

    <!-- Post Module -->
    <div class="material-post_container">

        <div class="material-post mdl-grid">
            <div class="mdl-card mdl-shadow--4dp mdl-cell mdl-cell--12-col">

                <!-- Post Header(Thumbnail & Title) -->
                
    <!-- Paradox Post Header -->
    
        <!-- Custom Thumbnail -->
        <div class="post_thumbnail-custom mdl-card__media mdl-color-text--grey-50" style="background-image:url(http://on2bs9q7q.bkt.clouddn.com/LinkedList.jpg)">
    
            <p class="article-headline-p">
                JDK底层实现源码分析系列(三) LinkedList源码分析
            </p>
        </div>





                
                    <!-- Paradox Post Info -->
                    <div class="mdl-color-text--grey-700 mdl-card__supporting-text meta">

    <!-- Author Avatar -->
    <div id="author-avatar">
        <img src="http://on2bs9q7q.bkt.clouddn.com/avatar.jpg" width="44px" height="44px" alt="Author Avatar"/>
    </div>
    <!-- Author Name & Date -->
    <div>
        <strong>Binux</strong>
        <span>3月 11, 2017</span>
    </div>

    <div class="section-spacer"></div>

    <!-- Favorite -->
    <!--
        <button id="article-functions-like-button" class="mdl-button mdl-js-button mdl-js-ripple-effect mdl-button--icon btn-like">
            <i class="material-icons" role="presentation">favorite</i>
            <span class="visuallyhidden">favorites</span>
        </button>
    -->

    <!-- Qrcode -->
    
        <button id="article-functions-qrcode-button" class="mdl-button mdl-js-button mdl-js-ripple-effect mdl-button--icon">
            <i class="material-icons" role="presentation">devices other</i>
            <span class="visuallyhidden">devices other</span>
        </button>
        <ul class="mdl-menu mdl-menu--bottom-right mdl-js-menu mdl-js-ripple-effect" for="article-functions-qrcode-button">
            <li class="mdl-menu__item">在其它设备中阅读本文章</li>
            <img src="">
        </ul>
    

    <!-- Tags (bookmark) -->
    
    <button id="article-functions-viewtags-button" class="mdl-button mdl-js-button mdl-js-ripple-effect mdl-button--icon">
        <i class="material-icons" role="presentation">bookmark</i>
        <span class="visuallyhidden">bookmark</span>
    </button>
    <ul class="mdl-menu mdl-menu--bottom-right mdl-js-menu mdl-js-ripple-effect" for="article-functions-viewtags-button">
        <li class="mdl-menu__item">
        <a class="post_tag-link" href="/tags/JDK/">JDK</a></li><li class="mdl-menu__item"><a class="post_tag-link" href="/tags/Source-Code/">Source Code</a>
    </ul>
    

    <!-- Share -->
    <button id="article-fuctions-share-button" class="mdl-button mdl-js-button mdl-js-ripple-effect mdl-button--icon">
    <i class="material-icons" role="presentation">share</i>
    <span class="visuallyhidden">share</span>
</button>
<ul class="mdl-menu mdl-menu--bottom-right mdl-js-menu mdl-js-ripple-effect" for="article-fuctions-share-button">
    

    
        
            <!-- Busuanzi Views -->
            <a class="post_share-link" href="#">
                <li class="mdl-menu__item">
                    <span id="busuanzi_container_page_pv">
                        <span id="busuanzi_value_page_pv"></span>&nbsp;浏览量
                    </span>
                </li>
            </a>
        
    

    <!-- Share Weibo -->
    
        <a class="post_share-link" href="http://service.weibo.com/share/share.php?appkey=&title=JDK底层实现源码分析系列(三) LinkedList源码分析&url=http://binux.cn//2017/03/11/LinkedList-Source-Code/index.html&pic=&searchPic=false&style=simple" target="_blank">
            <li class="mdl-menu__item">
                分享到微博
            </li>
        </a>
    

    <!-- Share Twitter -->
    

    <!-- Share Facebook -->
    

    <!-- Share Google+ -->
    
        <a class="post_share-link" href="https://plus.google.com/share?url=http://binux.cn//2017/03/11/LinkedList-Source-Code/index.html" target="_blank">
            <li class="mdl-menu__item">
                分享到 Google+
            </li>
        </a>
    

    <!-- Share LinkedIn -->
    

    <!-- Share QQ -->
    
        <a class="post_share-link" href="http://connect.qq.com/widget/shareqq/index.html?site=Binux Blog&title=JDK底层实现源码分析系列(三) LinkedList源码分析&summary=一名正在崛起的Java后端工程师&pics=http://binux.cnhttp://on2bs9q7q.bkt.clouddn.com/avatar.png&url=http://binux.cn/2017/03/11/LinkedList-Source-Code/index.html" target="_blank">
            <li class="mdl-menu__item">
                分享到 QQ
            </li>
        </a>
    

    <!-- Share Telegram -->
    
</ul>

</div>

                

                <!-- Post Content -->
                <div id="post-content" class="mdl-color-text--grey-700 mdl-card__supporting-text fade out">
    
        <blockquote>
<p>“合抱之木 生于毫末 九层之台 起于累土 千里之行 始于足下”</p>
</blockquote>
<h2 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h2><blockquote>
<p>JDK 版本1.7</p>
</blockquote>
<h3 id="Collection-大家族"><a href="#Collection-大家族" class="headerlink" title="Collection 大家族"></a>Collection 大家族</h3><center><img src="http://on2bs9q7q.bkt.clouddn.com/Java-Collections.png" alt="Collection"></center>

<blockquote>
<p>来源<a href="https://infinitescript.com/2014/10/java-collections-framework/" target="_blank" rel="external">Java Collections Framework</a></p>
</blockquote>
<h3 id="LinkedList-继承树"><a href="#LinkedList-继承树" class="headerlink" title="LinkedList 继承树"></a>LinkedList 继承树</h3><center><img src="http://on2bs9q7q.bkt.clouddn.com/LinkedList.png" alt="LinkedList"></center><br><center>LinkedList</center>

<p>LinkedList从数据结构层面上说算是一个双向链表 继承于AbstractSequentialList实现了List、Deque、Cloneable、Serializable</p>
<p>有三个重要的成员变量first(链表的头节点)、last(链表的尾节点)、size(链表的长度)</p>
<p>Node为存储数据的类 共有3个变量item(元素)、next(此元素的下一个节点)、prev(此元素的上一个节点)</p>
<hr>
<h2 id="分析"><a href="#分析" class="headerlink" title="分析"></a>分析</h2><h3 id="链表和数组"><a href="#链表和数组" class="headerlink" title="链表和数组"></a>链表和数组</h3><ul>
<li><p>数组：<br><br>数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。</p>
</li>
<li><p>链表：<br><br>链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。</p>
</li>
<li><p>区别：<br><br>数组静态分配内存，链表动态分配内存；<br><br>数组在内存中连续，链表不连续；<br><br>数组元素在栈区，链表元素在堆区；<br><br>数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；<br><br>数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。<br></p>
</li>
</ul>
<h3 id="new"><a href="#new" class="headerlink" title="new"></a>new</h3><p>LinkedList一共有俩个构造方法，一个是无参的，新new一个size为空的LinkedList，另一个是传入一个Collection类型的集合使用addAll(size,c)把集合中的全部数据加入到新建的LinkedList</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div></pre></td><td class="code"><pre><div class="line"><span class="comment">/**</span></div><div class="line"> * 在链表指定位置插入集合中所有数据</div><div class="line"> *</div><div class="line"> * <span class="doctag">@param</span> index index at which to insert the first element</div><div class="line"> *              from the specified collection</div><div class="line"> * <span class="doctag">@param</span> c collection containing elements to be added to this list</div><div class="line"> * <span class="doctag">@return</span> &#123;<span class="doctag">@code</span> true&#125; if this list changed as a result of the call</div><div class="line"> * <span class="doctag">@throws</span> IndexOutOfBoundsException &#123;<span class="doctag">@inheritDoc</span>&#125;</div><div class="line"> * <span class="doctag">@throws</span> NullPointerException if the specified collection is null</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">addAll</span><span class="params">(<span class="keyword">int</span> index, Collection&lt;? extends E&gt; c)</span> </span>&#123;</div><div class="line">    <span class="comment">// index &gt;= 0 &amp;&amp; index &lt;= size;</span></div><div class="line">    <span class="comment">// false throw new IndexOutOfBoundsException(outOfBoundsMsg(index));</span></div><div class="line">    checkPositionIndex(index);</div><div class="line"></div><div class="line">    Object[] a = c.toArray();</div><div class="line">    <span class="keyword">int</span> numNew = a.length;</div><div class="line">    <span class="keyword">if</span> (numNew == <span class="number">0</span>) <span class="comment">// 传入集合为空</span></div><div class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</div><div class="line"></div><div class="line">    Node&lt;E&gt; pred, succ;</div><div class="line">    <span class="comment">// pred为被插入节点前一个节点 succ为index节点 index&lt;size时用于移动index节点succ.prev = pred;</span></div><div class="line">    <span class="keyword">if</span> (index == size) &#123; <span class="comment">// 即插入链表的最后</span></div><div class="line">        succ = <span class="keyword">null</span>;</div><div class="line">        pred = last; <span class="comment">// 获取最后一个节点</span></div><div class="line">    &#125; <span class="keyword">else</span> &#123; <span class="comment">// 插入链表中间</span></div><div class="line">        succ = node(index);</div><div class="line">        pred = succ.prev; <span class="comment">// 获取index前一个节点</span></div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">for</span> (Object o : a) &#123;</div><div class="line"></div><div class="line">        E e = (E) o;</div><div class="line">        Node&lt;E&gt; newNode = <span class="keyword">new</span> Node&lt;&gt;(pred, e, <span class="keyword">null</span>);</div><div class="line">        <span class="comment">// 新new节点 pred指向 (index == size)(pred-&gt;last)</span></div><div class="line">        <span class="comment">// 新new节点 pred指向 (index &lt; size)(pred-&gt;succ.prev)</span></div><div class="line">        <span class="keyword">if</span> (pred == <span class="keyword">null</span>) <span class="comment">// 链表为空</span></div><div class="line">            first = newNode; <span class="comment">// 新节点为头节点</span></div><div class="line">        <span class="keyword">else</span></div><div class="line">            pred.next = newNode; <span class="comment">// 上次循环的节点的next设置为本次循环节点</span></div><div class="line">        pred = newNode; <span class="comment">// 设置下次循环的pred节点为本次循环增加的节点</span></div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">if</span> (succ == <span class="keyword">null</span>) &#123; <span class="comment">// index == size</span></div><div class="line">        last = pred; <span class="comment">// 设置last节点为循环的最后一个节点</span></div><div class="line">    &#125; <span class="keyword">else</span> &#123;</div><div class="line">        pred.next = succ; <span class="comment">// 设置循环的最后一个节点的next为index节点</span></div><div class="line">        succ.prev = pred; <span class="comment">// 设置设置index的prev为循环的最后一个节点</span></div><div class="line">    &#125;</div><div class="line"></div><div class="line">    size += numNew;</div><div class="line">    modCount++; <span class="comment">// fail-fast</span></div><div class="line">    <span class="keyword">return</span> <span class="keyword">true</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h3 id="插入数据"><a href="#插入数据" class="headerlink" title="插入数据"></a>插入数据</h3><p>LinkedList插入数据的方法有</p>
<ul>
<li>public boolean add(E e)</li>
<li>public void add(int index, E element)</li>
<li>public boolean addAll(Collection&lt;? extends E&gt; c)</li>
<li>public boolean addAll(int index, Collection&lt;? extends E&gt; c)</li>
<li>public void addFirst(E e)</li>
<li>public void addLast(E e)</li>
<li>private void linkFirst(E e)</li>
<li>void linkLast(E e)</li>
<li>void linkBefore(E e, Node<e> succ)</e></li>
<li>public boolean offerFirst(E e)</li>
<li>public boolean offerLast(E e)</li>
<li>public void push(E e)</li>
<li>public E set(int index, E element)</li>
<li>等</li>
</ul>
<blockquote>
<p>由于添加方法太多 本篇只会讲add(int index, E element) 其他插入方法都类似</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div></pre></td><td class="code"><pre><div class="line"><span class="comment">/**</span></div><div class="line"> * 在index之前插入element元素</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> index, E element)</span> </span>&#123;</div><div class="line">    checkPositionIndex(index);</div><div class="line">    <span class="comment">// 判断索引 index &gt;= 0 &amp;&amp; index &lt;= size</span></div><div class="line">    <span class="keyword">if</span> (index == size) <span class="comment">// 即链表尾部增加</span></div><div class="line">        linkLast(element);</div><div class="line">    <span class="keyword">else</span></div><div class="line">        linkBefore(element, node(index));</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="comment">/**</span></div><div class="line"> * 在index之前插入element元素 (建议画图看)</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">linkBefore</span><span class="params">(E e, Node&lt;E&gt; succ)</span> </span>&#123;</div><div class="line">    <span class="comment">// assert succ != null;</span></div><div class="line">    <span class="keyword">final</span> Node&lt;E&gt; pred = succ.prev; <span class="comment">// 获取index节点的前一个节点</span></div><div class="line">    <span class="keyword">final</span> Node&lt;E&gt; newNode = <span class="keyword">new</span> Node&lt;&gt;(pred, e, succ); <span class="comment">// 新建节点 赋值 把index的prev赋给新建节点prev</span></div><div class="line">    succ.prev = newNode; <span class="comment">// 设置index节点的prev为新节点</span></div><div class="line">    <span class="keyword">if</span> (pred == <span class="keyword">null</span>) <span class="comment">// 即链表为空</span></div><div class="line">        first = newNode; <span class="comment">// 设置新节点为头节点</span></div><div class="line">    <span class="keyword">else</span></div><div class="line">        pred.next = newNode; <span class="comment">// 设置index节点的前一个节点的下个节点为newNode</span></div><div class="line">    size++;</div><div class="line">    modCount++;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h3 id="删除数据"><a href="#删除数据" class="headerlink" title="删除数据"></a>删除数据</h3><p>LinkedList删除数据的方法有</p>
<ul>
<li>public void clear()</li>
<li>public E poll()</li>
<li>public E remove()</li>
<li>public E remove(int index)</li>
<li>public boolean remove(Object o)</li>
<li>public E removeFirst()</li>
<li>public boolean removeFirstOccurrence(Object o)</li>
<li>public boolean removeLastOccurrence(Object o)</li>
<li>public E removeLast()</li>
<li>public E pollFirst()</li>
<li>public E pollLast()</li>
<li>public E pop()</li>
<li>private E unlinkFirst(Node<e> f)</e></li>
<li>等</li>
</ul>
<p>由于方法太多 而且都类似 本篇只会选择unlinkFirst()方法分析<br><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div></pre></td><td class="code"><pre><div class="line"><span class="comment">/**</span></div><div class="line"> * 移除first节点</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">private</span> E <span class="title">unlinkFirst</span><span class="params">(Node&lt;E&gt; f)</span> </span>&#123;</div><div class="line">    <span class="comment">// assert f == first &amp;&amp; f != null;</span></div><div class="line">    <span class="keyword">final</span> E element = f.item; <span class="comment">// 获取first的元素</span></div><div class="line">    <span class="keyword">final</span> Node&lt;E&gt; next = f.next; <span class="comment">// 获取first的下一个元素</span></div><div class="line">    f.item = <span class="keyword">null</span>; <span class="comment">// 删除first的元素</span></div><div class="line">    f.next = <span class="keyword">null</span>; <span class="comment">// 删除first指向的元素 让GC回收</span></div><div class="line">    first = next; <span class="comment">// 设置first为删除节点的下一个节点</span></div><div class="line">    <span class="keyword">if</span> (next == <span class="keyword">null</span>) <span class="comment">// 下个节点为空</span></div><div class="line">        last = <span class="keyword">null</span>; <span class="comment">// 说明只有一个first节点不为null</span></div><div class="line">    <span class="keyword">else</span></div><div class="line">        next.prev = <span class="keyword">null</span>; <span class="comment">// 设置first的下个节点为null</span></div><div class="line">    size--;</div><div class="line">    modCount++;</div><div class="line">    <span class="keyword">return</span> element; <span class="comment">// 返回删除数据</span></div><div class="line">&#125;</div></pre></td></tr></table></figure></p>
<h3 id="修改数据"><a href="#修改数据" class="headerlink" title="修改数据"></a>修改数据</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div></pre></td><td class="code"><pre><div class="line"><span class="comment">/**</span></div><div class="line"> * 替换指定位置的元素</div><div class="line"> *</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">public</span> E <span class="title">set</span><span class="params">(<span class="keyword">int</span> index, E element)</span> </span>&#123;</div><div class="line">    checkElementIndex(index); <span class="comment">// 检查index是否越界</span></div><div class="line">    Node&lt;E&gt; x = node(index); <span class="comment">// 获得指定index元素</span></div><div class="line">    E oldVal = x.item; <span class="comment">// 活动被替换的元素</span></div><div class="line">    x.item = element; <span class="comment">// 修改元素</span></div><div class="line">    <span class="keyword">return</span> oldVal; <span class="comment">// 返回被修改的元素</span></div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h3 id="查询数据"><a href="#查询数据" class="headerlink" title="查询数据"></a>查询数据</h3><p>LinkedList查询数据的方法有</p>
<ul>
<li>public E getFirst():获取First节点元素</li>
<li>public E getLast():获取Last节点元素</li>
<li>Node<e> node(int index):获取指定index节点元素</e></li>
<li>public E peek():获取First节点元素</li>
<li>public E peekFirst():获取First节点元素</li>
<li>public E peekLast():获取Last节点元素</li>
<li>public E poll():删除First节点并返回删除元素</li>
<li>public E pollFirst():删除First节点并返回删除元素</li>
<li>public E pollLast():删除Last节点并返回删除元素</li>
<li>public E pop():删除First节点并返回删除元素</li>
<li>等</li>
</ul>
<p>由于方法太多 而且都类似 本篇只会选择get()方法分析<br><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div></pre></td><td class="code"><pre><div class="line"><span class="comment">/**</span></div><div class="line"> * 获取指定index元素</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">public</span> E <span class="title">get</span><span class="params">(<span class="keyword">int</span> index)</span> </span>&#123;</div><div class="line">    checkElementIndex(index);</div><div class="line">    <span class="keyword">return</span> node(index).item;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="comment">/**</span></div><div class="line"> * 返回指定index的节点元素 会更具index的值判断是从前找还是从后找</div><div class="line"> */</div><div class="line"><span class="function">Node&lt;E&gt; <span class="title">node</span><span class="params">(<span class="keyword">int</span> index)</span> </span>&#123;</div><div class="line">    <span class="comment">// assert isElementIndex(index);</span></div><div class="line"></div><div class="line">    <span class="keyword">if</span> (index &lt; (size &gt;&gt; <span class="number">1</span>)) &#123; <span class="comment">// index &lt; size / 2</span></div><div class="line">        Node&lt;E&gt; x = first;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; index; i++)</div><div class="line">            x = x.next;</div><div class="line">        <span class="keyword">return</span> x;</div><div class="line">    &#125; <span class="keyword">else</span> &#123; <span class="comment">// index &gt; size / 2</span></div><div class="line">        Node&lt;E&gt; x = last;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = size - <span class="number">1</span>; i &gt; index; i--)</div><div class="line">            x = x.prev;</div><div class="line">        <span class="keyword">return</span> x;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>
<hr>
<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><p>LinkedList本质上就是一个双向链表，不会像ArrayList那样，空间不足时去扩容(array copy是一件效率非常低的操作)这样做的好处就是处理大量数据时，存储数据的时间比ArrayList要低很多。</p>
<p>另外LinkedList实现了Deque接口，可以通过内部,实现FIFO(先进先出)的队列或者LIFO(后进先出)的栈</p>
<hr>
<h2 id="著作权声明"><a href="#著作权声明" class="headerlink" title="著作权声明"></a>著作权声明</h2><p>本文首次发布于 <a href="http://binux.cn">Binux Blog</a>，转载请保留以上链接</p>

    

    
</div>


                

                <!-- Post Comments -->
                
                    




    <!-- 使用 DISQUS_CLICK -->
    <div id="disqus-comment">	
        <div id="disqus_thread"></div>
<!-- include js -->
<script src="/js/ripple.js"></script>

<!-- add animation -->
<style>
        .ripple-container {
        }
        .ripple-container .ripple{
            background-color: rgba(255,255,255,0.4);
            animation: ripple 2s forwards cubic-bezier(0, 0, 0.2, 1);
        }
        @keyframes ripple {
            0% {
                transform: scale(0);
                opacity: 1;
            }
            80% {
                transform: scale(1);
            }
            100% {
                opacity: 0;
            }
        }
		.disqus_click_btn {
            background-color: dodgerblue;
            color: white;
            padding: 10px 20px;
            border:0;
            font-size: 14px;
            cursor: pointer
        }
</style>
	
<!-- add data-ripple attribute -->
<div class="btn_click_load"> 
    <button class="disqus_click_btn" data-ripple>阅读评论 「请确保 disq.us &amp; disquscdn.com &amp; disqus.com 可以正常加载」</button>
</div>
	
<script>
    // add effect to elements
    Array.prototype.forEach.call(document.querySelectorAll('[data-ripple]'), function(element){
        // find all elements and attach effect
        new RippleEffect(element); // element is instance of javascript element node
    });
</script>

<script>
    $('.btn_click_load').click(function() {  //click to load comments
        var disqus_config = function () {
            this.page.url = 'http://binux.cn/2017/03/11/LinkedList-Source-Code/index.html';  // Replace PAGE_URL with your page's canonical URL variable
            this.page.identifier = PAGE_IDENTIFIER; // Replace PAGE_IDENTIFIER with your page's unique identifier variable
        };
        (function() { // DON'T EDIT BELOW THIS LINE
            var d = document;
            var s = d.createElement('script');
            s.src = '//xubinux.disqus.com/embed.js';
            s.setAttribute('data-timestamp', + new Date());
            (d.head || d.body).appendChild(s);
        })();
        $('.btn_click_load').css('display','none');
    });
</script>
  	

    </div>
    <style>
        #disqus-comment{
            background-color: #eee;
            padding: 2pc;
        }
    </style>

                
            </div>

            <!-- Post Prev & Next Nav -->
            <nav class="material-nav mdl-color-text--grey-50 mdl-cell mdl-cell--12-col">
    <!-- Prev Nav -->
    
        <a href="/2017/03/12/Hello-Hexo/" id="post_nav-newer" class="prev-content">
            <button class="mdl-button mdl-js-button mdl-js-ripple-effect mdl-button--icon mdl-color--white mdl-color-text--grey-900" role="presentation">
                <i class="material-icons">arrow_back</i>
            </button>
            &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
            新篇
        </a>
    

    <!-- Section Spacer -->
    <div class="section-spacer"></div>

    <!-- Next Nav -->
    
        <a href="/2017/03/09/Alibaba-Arithmetic/" id="post_nav-older" class="next-content">
            旧篇
            &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
            <button class="mdl-button mdl-js-button mdl-js-ripple-effect mdl-button--icon mdl-color--white mdl-color-text--grey-900" role="presentation">
                <i class="material-icons">arrow_forward</i>
            </button>
        </a>
    
</nav>

        </div>
    </div>



                    
                        <!-- Overlay For Active Sidebar -->
<div class="sidebar-overlay"></div>

<!-- Material sidebar -->
<aside id="sidebar" class="sidebar sidebar-colored sidebar-fixed-left" role="navigation">
    <div id="sidebar-main">
        <!-- Sidebar Header -->
        <div class="sidebar-header header-cover" style="background-image: url(http://on2bs9q7q.bkt.clouddn.com/sidebar_header.png);">
    <!-- Top bar -->
    <div class="top-bar"></div>

    <!-- Sidebar toggle button -->
    <button type="button" class="sidebar-toggle mdl-button mdl-js-button mdl-js-ripple-effect mdl-button--icon" style="display: initial;" data-upgraded=",MaterialButton,MaterialRipple">
        <i class="material-icons">clear_all</i>
        <span class="mdl-button__ripple-container">
            <span class="mdl-ripple">
            </span>
        </span>
    </button>

    <!-- Sidebar Avatar -->
    <div class="sidebar-image">
        <img src="http://on2bs9q7q.bkt.clouddn.com/avatar.jpg" alt="Binux's avatar">
    </div>

    <!-- Sidebar Email -->
    <a data-toggle="dropdown" class="sidebar-brand" href="#settings-dropdown">
        xu.binux@gmail.com
        <b class="caret"></b>
    </a>
</div>


        <!-- Sidebar Navigation  -->
        <ul class="nav sidebar-nav">
    <!-- User dropdown  -->
    <li class="dropdown">
        <ul id="settings-dropdown" class="dropdown-menu">
            
                <li>
                    <a href="Mailto:xu.binux@gmail.com?Subject=网友来信（来自博客）" target="_blank" title="Email Me">
                        
                            <i class="material-icons sidebar-material-icons sidebar-indent-left1pc-element">email</i>
                        
                        Email Me
                    </a>
                </li>
            
        </ul>
    </li>

    <!-- Homepage -->
    
        <li id="sidebar-first-li">
            <a href="/" target="_self">
                
                    <i class="material-icons sidebar-material-icons">home</i>
                
                主页
            </a>
        </li>
        
    

    <!-- Archives  -->
    
        <li class="dropdown">
            <a href="#" class="ripple-effect dropdown-toggle" data-toggle="dropdown">
                
                    <i class="material-icons sidebar-material-icons">inbox</i>
                
                    归档
                <b class="caret"></b>
            </a>
            <ul class="dropdown-menu">
            <li>
                <a class="sidebar_archives-link" href="/archives/2017/05/">五月 2017<span class="sidebar_archives-count">2</span></a></li><li><a class="sidebar_archives-link" href="/archives/2017/04/">四月 2017<span class="sidebar_archives-count">1</span></a></li><li><a class="sidebar_archives-link" href="/archives/2017/03/">三月 2017<span class="sidebar_archives-count">17</span></a></li><li><a class="sidebar_archives-link" href="/archives/2017/02/">二月 2017<span class="sidebar_archives-count">3</span></a>
            </ul>
        </li>
        
    

    <!-- Categories  -->
    
        <li class="dropdown">
            <a href="#" class="ripple-effect dropdown-toggle" data-toggle="dropdown">
                
                    <i class="material-icons sidebar-material-icons">chrome_reader_mode</i>
                
                分类
                <b class="caret"></b>
            </a>
            <ul class="dropdown-menu">
                <li>
                <a class="sidebar_archives-link" href="/categories/Bug/">Bug<span class="sidebar_archives-count">3</span></a></li><li><a class="sidebar_archives-link" href="/categories/安装教程/">安装教程<span class="sidebar_archives-count">8</span></a></li><li><a class="sidebar_archives-link" href="/categories/工具/">工具<span class="sidebar_archives-count">1</span></a></li><li><a class="sidebar_archives-link" href="/categories/源码分析/">源码分析<span class="sidebar_archives-count">7</span></a></li><li><a class="sidebar_archives-link" href="/categories/随记/">随记<span class="sidebar_archives-count">3</span></a></li><li><a class="sidebar_archives-link" href="/categories/面试题/">面试题<span class="sidebar_archives-count">1</span></a>
            </ul>
        </li>
        
            <li class="divider"></li>
        
    

    <!-- Pages  -->
    
        <li>
            <a href="/about" title="About ME">
                
                    <i class="material-icons sidebar-material-icons">person</i>
                
                About ME
            </a>
        </li>
        
    
        <li>
            <a href="/portfolio" title="Portfolio">
                
                    <i class="material-icons sidebar-material-icons">reorder</i>
                
                Portfolio
            </a>
        </li>
        
    
        <li>
            <a href="/gallery" title="Gallery">
                
                    <i class="material-icons sidebar-material-icons">photo</i>
                
                Gallery
            </a>
        </li>
        
    
        <li>
            <a href="/tags" title="Tags">
                
                    <i class="material-icons sidebar-material-icons">bookmark</i>
                
                Tags
            </a>
        </li>
        
    
        <li>
            <a href="/links" title="Links">
                
                    <i class="material-icons sidebar-material-icons">people</i>
                
                Links
            </a>
        </li>
        
            <li class="divider"></li>
        
    

    <!-- Article Number  -->
    
        <li>
            <a href="/archives">
                文章总数
                <span class="sidebar-badge">23</span>
            </a>
        </li>
        
    
</ul>


        <!-- Sidebar Footer -->
        <!--
I'm glad you use this theme, the development is no so easy, I hope you can keep the copyright, I will thank you so much.
If you still want to delete the copyrights, could you still retain the first one? Which namely "Theme Material"
It will not impact the appearance and can give developers a lot of support :)

很高兴您使用并喜欢该主题，开发不易 十分谢谢与希望您可以保留一下版权声明。
如果您仍然想删除的话 能否只保留第一项呢？即 "Theme Material"
它不会影响美观并可以给开发者很大的支持和动力。 :)
-->

<!-- Sidebar Divider -->


<!-- Theme Material -->

    <a href="https://github.com/viosey/hexo-theme-material"  class="sidebar-footer-text-a" target="_blank">
        <div class="sidebar-text mdl-button mdl-js-button mdl-js-ripple-effect sidebar-footer-text-div" data-upgraded=",MaterialButton,MaterialRipple">
            主题 - Material
            <span class="sidebar-badge badge-circle">i</span>
        </div>
    </a>


<!-- Help & Support -->
<!--

-->

<!-- Feedback -->
<!--

-->

<!-- About Theme -->
<!--

-->

    </div>

    <!-- Sidebar Image -->
    

</aside>

                    

                    
                        <!-- Footer Top Button -->
                        <div class="toTop-wrap">
    <a href="#top" class="toTop">
        <i class="material-icons footer_top-i">expand_less</i>
    </a>
</div>

                    

                    <!--Footer-->
<footer class="mdl-mini-footer" id="bottom">
    
        <!-- Paradox Footer Left Section -->
        <div class="mdl-mini-footer--left-section sns-list">
    <!-- Twitter -->
    

    <!-- Facebook -->
    

    <!-- Google + -->
    

    <!-- Weibo -->
    
        <a href="http://weibo.com/xubin0830" target="_blank">
            <button class="mdl-mini-footer--social-btn social-btn" style="background-image: url(/img/footer/footer_ico-weibo.png);">
                <span class="visuallyhidden">Weibo</span>
            </button><!--
     --></a>
    

    <!-- Instagram -->
    

    <!-- Tumblr -->
    

    <!-- Github -->
    
        <a href="https://github.com/xubinux" target="_blank">
            <button class="mdl-mini-footer--social-btn social-btn" style="background-image: url(/img/footer/footer_ico-github.png);">
                <span class="visuallyhidden">Github</span>
            </button><!--
     --></a>
    

    <!-- LinkedIn -->
    

    <!-- Zhihu -->
    
        <a href="https://www.zhihu.com/people/binux-29/" target="_blank">
            <button class="mdl-mini-footer--social-btn social-btn" style="background-image: url(/img/footer/footer_ico-zhihu.png);">
                <span class="visuallyhidden">Zhihu</span>
            </button><!--
     --></a>
    

    <!-- Bilibili -->
    

    <!-- Telegram -->
    
</div>


        <!--Copyright-->
        <div id="copyright">
            Copyright&nbsp;©&nbsp;
            <script type="text/javascript">
                var fd = new Date();
                document.write(fd.getFullYear());
            </script>
            &nbsp;Binux Blog
        </div>

        <!-- Paradox Footer Right Section -->

        <!--
        I am glad you use this theme, the development is no so easy, I hope you can keep the copyright.
        It will not impact the appearance and can give developers a lot of support :)

        很高兴您使用该主题，开发不易，希望您可以保留一下版权声明。
        它不会影响美观并可以给开发者很大的支持。 :)
        -->

        <div class="mdl-mini-footer--right-section">
            <div>
                <div class="footer-develop-div">Powered by <a href="https://hexo.io" target="_blank" class="footer-develop-a">Hexo</a></div>
                <div class="footer-develop-div">Theme - <a href="https://github.com/viosey/hexo-theme-material" target="_blank" class="footer-develop-a">Material</a></div>
            </div>
        </div>
    
</footer>


                    <!-- Import File -->
<script src="/js/lazyload.min.js"></script>
<script src="/js/js.min.js"></script>
<script src="/js/nprogress.js"></script>

<script type="text/javascript">
    NProgress.configure({
        showSpinner: true
    });
    NProgress.start();
    $('#nprogress .bar').css({
        'background': '#29d'
    });
    $('#nprogress .peg').css({
        'box-shadow': '0 0 10px #29d, 0 0 15px #29d'
    });
    $('#nprogress .spinner-icon').css({
        'border-top-color': '#29d',
        'border-left-color': '#29d'
    });
    setTimeout(function() {
        NProgress.done();
        $('.fade').removeClass('out');
    }, 800);
</script>



    <script src="/js/smoothscroll.js"></script>





    <!-- Busuanzi -->
    <script src="https://dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>







<!-- Swiftye -->


<!-- Local Search-->

    <script>
    var searchFunc = function(path, search_id, content_id) {
        'use strict';
        $.ajax({
            url: path,
            dataType: 'xml',
            success: function( xmlResponse ) {
                // get the contents from search data
                var datas = $( 'entry', xmlResponse ).map(function() {
                    return {
                        title: $( 'title', this ).text(),
                        content: $('content',this).text(),
                        url: $( 'url' , this).text()
                    };
                }).get();
                var $input = document.getElementById(search_id);
                var $resultContent = document.getElementById(content_id);
                $input.addEventListener('input', function() {
                    var str='<ul class=\"search-result-list\">';
                    var keywords = this.value.trim().toLowerCase().split(/[\s\-]+/);
                    $resultContent.innerHTML = '';
                    if (this.value.trim().length <= 0) {
                        return;
                    }
                    // perform local searching
                    datas.forEach(function(data) {
                        var isMatch = true;
                        var content_index = [];
                        var data_title = data.title.trim().toLowerCase();
                        var data_content = data.content.trim().replace(/<[^>]+>/g,'').toLowerCase();
                        var data_url = data.url;
                        var index_title = -1;
                        var index_content = -1;
                        var first_occur = -1;
                        // only match artiles with not empty titles and contents
                        if(data_title !== '' && data_content !== '') {
                            keywords.forEach(function(keyword, i) {
                                index_title = data_title.indexOf(keyword);
                                index_content = data_content.indexOf(keyword);
                                if( index_title < 0 && index_content < 0 ) {
                                    isMatch = false;
                                } else {
                                    if (index_content < 0) {
                                        index_content = 0;
                                    }
                                    if (i === 0) {
                                        first_occur = index_content;
                                    }
                                }
                            });
                        }
                        // show search results
                        if (isMatch) {
                            str += '<li><a href="'+ data_url +'" class="search-result-title" target="_blank">'+ data_title;
                            var content = data.content.trim().replace(/<[^>]+>/g, '');
                            if (first_occur >= 0) {
                                // cut out characters
                                var start = first_occur - 6;
                                var end = first_occur + 6;
                                if (start < 0) {
                                    start = 0;
                                }
                                if (start === 0) {
                                    end = 10;
                                }
                                if (end > content.length) {
                                    end = content.length;
                                }
                                var match_content = content.substr(start, end);
                                // highlight all keywords
                                keywords.forEach(function(keyword) {
                                    var regS = new RegExp(keyword, 'gi');
                                    match_content = match_content.replace(regS, '<em class="search-keyword">'+keyword+'</em>');
                                })
                                str += '<p class="search-result">' + match_content + '...</p>' +'</a>';
                            }
                        }
                    });
                    $resultContent.innerHTML = str;
                });
            }
        });
    }
</script>


    <script>
        var inputArea = document.querySelector('#search');
        var getSearchFile = function() {
            var path = 'search.xml';
            searchFunc(path, 'search', 'local-search-result');
        }

        if(inputArea) {
            inputArea.onfocus = function() {
                getSearchFile();
            }
        }
    </script>


<!-- Window Load-->
<script>
    $(window).load(function() {
        // Post_Toc parent position fixed
        $('.post-toc-wrap').parent('.mdl-menu__container').css('position', 'fixed');
    });
</script>

<!-- MathJax Load-->


                </main>
            </div>
        </body>
    
</html>
